package org.example.myleet.p672;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {
    public int flipLights(int n, int presses) {
        if (presses == 0) {
            return 1;
        }
        //周期为2*3=6，考虑到不足6个的情况，最多12个灯泡可以知道所有的情况
        if (n > 12) {
            n %= 12;
        }
        int p = presses;
        //模拟出4个开关，采用异或运算进行灯泡翻转
        int switch1 = 1;
        for (int i = 1; i < n; ++i) {
            switch1 <<= 1;
            switch1 += 1;
        }
        int switch2 = n > 1 ? 0b10 : 0;
        for (int i = 1; i < n / 2; ++i) {
            switch2 <<= 2;
            switch2 += 2;
        }
        int switch3 = 0b01;
        for (int i = 1; i < (n + 1) / 2; ++i) {
            switch3 <<= 2;
            switch3 += 1;
        }
        int switch4 = 0b001;
        for (int i = 1; i < n / 2; ++i) {
            switch4 <<= 3;
            switch4 += 1;
        }
        //BFS模拟开关过程
        int situation = switch1;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(situation);
        while (!queue.isEmpty() && p > 0) {
            int size = queue.size();
            //情况去重
            Set<Integer> curSituations = new HashSet<>(switch1);
            for (int i = 0; i < size; ++i) {
                situation = queue.poll();
                //开关 1 ：反转当前所有灯的状态
                int situation1 = switch1 ^ situation;
                if (curSituations.add(situation1)) {
                    queue.offer(situation1);
                }
                //开关 2 ：反转编号为偶数的灯的状态
                int situation2 = switch2 ^ situation;
                if (curSituations.add(situation2)) {
                    queue.offer(situation2);
                }
                //开关 3 ：反转编号为奇数的灯的状态
                int situation3 = switch3 ^ situation;
                if (curSituations.add(situation3)) {
                    queue.offer(situation3);
                }
                //开关 4 ：反转编号为 j = 3k + 1 的灯的状态
                int situation4 = switch4 ^ situation;
                if (curSituations.add(situation4)) {
                    queue.offer(situation4);
                }
            }
            --p;
        }
        //取最后一次拨完开关之后剩下的情况数量
        return queue.size();
    }
}
